import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class TreeBuilder {
	private Node root;
	private LinkedList<Node> visited;

	 private ArrayList<String[][]> resultTable;

	public TreeBuilder(int[][] table, int[][] output)
	{
		Node.setTable(table, output);
	}

	public ArrayList<String> solveSimpleControl(int start, int end)
	{
		root = new SimpleControl(start, end);
		return solve();
	}

	public ArrayList<String> solveTerminal()
	{
		int statesNo = Node.nextState.length;

		// Initializing the root group that contains all states
		ArrayList<ArrayList<Integer>> groups = new ArrayList<ArrayList<Integer>>(
				1);
		ArrayList<Integer> rootGroup = new ArrayList<Integer>(statesNo);
		groups.add(rootGroup);
		for (int i = 0; i < statesNo; i++)
			rootGroup.add(i);

		// Initializing the root group output that is empty
		ArrayList<String> groupOutput = new ArrayList<String>(1);
		groupOutput.add("");

		root = new TerminalState("", groups, groupOutput);

		return solve();
	}

	public ArrayList<String> solveSynchronization()
	{
		int states = Node.nextState.length;
		ArrayList<Integer> arr = new ArrayList<Integer>(states);
		for (int i = 0; i < states; i++)
			arr.add(i);
		root = new TerminalSynchronization(arr, "");
		return solve();
	}

	private ArrayList<String> solve()
	{
		// exploring tree using BFS
		Queue<Node> queue = new LinkedList<Node>();
		queue.add(root);
		queue.add(null);

		Queue<Node> level = new LinkedList<Node>();
		visited = new LinkedList<Node>();
		
		visited.add(root);
		
		resultTable = new ArrayList<String[][]>();
		ArrayList<String> sequences = new ArrayList<String>();
		
		boolean done = false;
		while (!queue.isEmpty())
		{
			Node front = queue.poll();
			if (front == null) // this flag for representing the end of level
			{
				// checking that this level found a solution
				// if yes break as shortest solution(s) was found 
				if(done) 
					break;
				while (!level.isEmpty())
					// adding the visited node of the last level
					visited.add(level.poll());
				if(!queue.isEmpty())
					queue.add(null);
			} else
			{
				if (front.isTerminated())
				{
					// the node has been terminated by stopping condition
					// Get the result from Node
					done = true;
					sequences.add(front.getResult());
					resultTable.add(front.getTable());
				} else
				{
					// going further in this branch
					Node leftChild = front.ApplyZero();
					Node rightChild = front.ApplyOne();
					if (!wasVisited(leftChild)){
						queue.add(leftChild);
						level.add(leftChild);
					}

					if (!wasVisited(rightChild)){
						queue.add(rightChild);
						level.add(rightChild);
					}
				}
			}
		}
		return sequences;
	}

	/**
	 * this method return whether this node was visited in higher level or not
	 */
	private boolean wasVisited(Node e)
	{
		for (Node prev : visited)
			if (e.isEqual(prev))
				return true;
		return false;
	}
	public ArrayList<String[][]> getResultTable()
	{
		return resultTable;
	}	
}
